#include <bits/stdc++.h>
using namespace std;
#define int long long

int a[50004];

signed main() {
	freopen("escape.in", "w", stdout);
	int n = 30000, m = 30000;
	mt19937 rnd(time(0));
	cout << n << " " << m << "\n";
	a[1] = 1;
	for (int i = 2; i <= n; ++i) {
		a[i] = i;
		cout << (rnd() % (i - 1)) + 1 << " \n"[i == n];
	}
	for (int i = 2; i <= n; ++i) {
		swap(a[i], a[rnd() % (i - 1) + 1]);
	}
	for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
	for (int i = 1; i <= m; ++i) {
		int l = rnd() % n + 1;
		int r = max(min((int)(rnd() % n + 1), l + 99), l - 99);
		if (l > r) swap(l, r);
		cout << l << " " << r << "\n";
	}

}
